/*
 * Copyright (C), 2015-2018
 * FileName: Solution063
 * Author:   zhao
 * Date:     2018/12/14 14:31
 * Description: 63. 不同路径 II
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

/**
 * 〈一句话功能简述〉<br>
 * 〈63. 不同路径 II〉
 *
 * @author zhao
 * @date 2018/12/14 14:31
 * @since 1.0.0
 */
public class Solution063 {
  /**************************************
   * 题目

   一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

   机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

   现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？



   网格中的障碍物和空位置分别用 1 和 0 来表示。

   说明：m 和 n 的值均不超过 100。

   示例 1:

   输入:
   [
   [0,0,0],
   [0,1,0],
   [0,0,0]
   ]
   输出: 2
   解释:
   3x3 网格的正中间有一个障碍物。
   从左上角到右下角一共有 2 条不同的路径：
   1. 向右 -> 向右 -> 向下 -> 向下
   2. 向下 -> 向下 -> 向右 -> 向右
   **************************************/

  /*************************************
   想法：
      用上62题的题解，在循环中加上障碍物的判断就解决呢

   我的做法
   超过93%的测试案例
   时间复杂度/空间复杂度：n*m/n
   代码执行过程：

   总结：

   ************************************/
  public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if (obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
      return 0;
    }

    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;

    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (obstacleGrid[i][j] == 1) {
          dp[i][j] = 0;
        } else {
          if (i == 0 && j == 0) {
            dp[i][j] = 1;
            continue;
          }
          if (i == 0) {
            dp[i][j] = dp[i][j - 1];
            continue;
          }
          if (j == 0) {
            dp[i][j] = dp[i - 1][j];
            continue;
          }
          dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
      }
    }
    return dp[m - 1][n - 1];

  }

  /**************************************
   * 比我好的答案 better
   * ***********************************/
  public int better(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    int[] res = new int[n];
    res[0] = 1;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (obstacleGrid[i][j] == 1) {
          res[j] = 0;
        } else if (j > 0) {
          res[j] = res[j] + res[j - 1];
        }
      }
    }
    return res[n - 1];
  }
}